package 每日一题;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-12
 **/

public class No29两数相除 {

    /**
     * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
     * 返回被除数 dividend 除以除数 divisor 得到的商。
     * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
     * <p>
     * 示例 1:
     * 输入: dividend = 10, divisor = 3
     * 输出: 3
     * 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
     * 示例 2:
     * 输入: dividend = 7, divisor = -3
     * 输出: -2
     * 解释: 7/-3 = truncate(-2.33333..) = -2
     *  
     * 提示：
     * 被除数和除数均为 32 位有符号整数。
     * 除数不为 0。
     * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。
     * 本题中，如果除法结果溢出，则返回 231 − 1。
     */

    private long dividend;
    private long divisor;

    public int divide(int dividend, int divisor) {

        if (dividend == divisor) {
            return 1;
        }

        if (dividend == 0) {
            return 0;
        }

        boolean positive = true;

        if (dividend < 0 && divisor < 0) {
            positive = true;
        } else if (dividend < 0 || divisor < 0) {
            positive = false;
        }

        this.dividend = Math.abs((long) dividend);
        this.divisor = Math.abs((long) divisor);

        if (this.dividend < this.divisor) {
            return 0;
        }

        // 不能用乘法,除法,取模

        long result = this.recursion(this.dividend);

        if (result > Integer.MAX_VALUE && positive) {
            return Integer.MAX_VALUE;
        }

        return (int) (positive ? result : -result);
    }

    private long recursion(long num) {

        if (num == this.divisor) {
            return 1;
        }

        if (num < this.divisor) {
            return 0;
        }

        int count = 1;
        long curNum = this.divisor;

        while ((curNum << 1) < num && curNum < Integer.MAX_VALUE << 1) {
            // 乘2
            curNum <<= 1;
            count <<= 1;
        }

        return count + this.recursion(num - curNum);
    }

    public static void main(String[] args) {
        No29两数相除 n = new No29两数相除();
        int result = n.divide(Integer.MIN_VALUE, -1);
        System.out.println(result);
    }

}
